package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 935. 骑士拨号器
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/19 21:53
 */
public class KnightDialer {

    public static void main(String[] args) {
        KnightDialer test = new KnightDialer();

        // 46
        int n = 3;

        // 986742198
//        int n = 30;

        int i = test.knightDialer(n);
        System.out.println(i);
    }

    public int knightDialer(int n) {
        if (n < 3) {
            return n * 10;
        }
        long[] arr1 = new long[9];
        long[] arr2 = new long[9];
        int[][] arr = {{4, 5}, {5, 7}, {6, 8}, {4, 7}, {0, 3, 8}, {0, 1, 6}, {2, 5}, {1, 3}, {2, 4}, {4, 5}};
        Arrays.fill(arr1, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 9; j++) {
                int[] ints = arr[j];
                for (int v : ints) {
                    arr2[v] += arr1[j];
                }
            }
            for (int j = 0; j < 9; j++) {
                arr1[j] = arr2[j] % 1000000007;
                arr2[j] = 0;
            }
        }
        long sum = 0;
        for (int i = 0; i < 9; i++) {
            sum += arr1[i] % 1000000007;
        }
        return (int) (sum % 1000000007);
    }


    public int knightDialer2(int n) {
        if (n < 3) {
            return n * 10;
        }
        long[] arr1 = new long[10];
        long[] arr2 = new long[10];
        int[][] arr = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}, {4, 6}};
        Arrays.fill(arr1, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                int[] ints = arr[j];
                for (int v : ints) {
                    arr2[v] += arr1[j];
                }
            }
            for (int j = 0; j < 10; j++) {
                arr1[j] = arr2[j] % 1000000007;
                arr2[j] = 0;
            }
        }
        long sum = 0;
        for (int i = 0; i < 10; i++) {
            sum += arr1[i] % 1000000007;
        }
        return (int) (sum % 1000000007);
    }

}
